package study.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

//逆波兰计算器
public class PolandNotation2 {
    public static void main(String[] args) {
        //rpn();

        String exp = "1+((2+3)*4)-5";
        List<String> list = infixToArrayList(exp);
        System.out.println(list);

        List<String> suffixExpressionList = parseSuffixExpressionList(list);
        System.out.println(suffixExpressionList);

        int calculate = calculate(suffixExpressionList);
        System.out.println(calculate);
    }

    public static List<String> parseSuffixExpressionList(List<String> list){
        //符号桟
        Stack<String> charStack = new Stack<>();
        //数据桟
        List<String> resultStack = new ArrayList<>();

        //遍历list
        for (String item : list) {
            //如果item是一个数，放到数据桟resultStack
            if (item.matches("\\d+")){
                resultStack.add(item);
            }else if ("(".equals(item)){
                charStack.push(item);
            }else if (")".equals(item)){//如果是右括号)，就将符号桟的内容弹出，直到遇到左括号
                //如果不是小括号，就将符号桟的内容弹出并加入到结果桟，直到遇到左括号，停止遍历
                while (!"(".equals(charStack.peek())){
                    resultStack.add(charStack.pop());
                }
                //然后将左括号也弹出，消除一对小括号
                charStack.pop();
            }else { //剩余的就是运算符的情况了
                //先比较运算符的优先级
                while (!charStack.isEmpty() &&
                        Operator.getPriority(item) <= Operator.getPriority(charStack.peek())) {
                    resultStack.add(charStack.pop());
                }
                charStack.push(item);
            }
        }

        while (!charStack.isEmpty()){
            resultStack.add(charStack.pop());
        }

        return resultStack;
    }

    //将中缀表达式转成ArrayList
    //1+(2+3)*4-5
    public static List<String> infixToArrayList(String s){
        List<String> list = new ArrayList<>();
        int i = 0;  //指针，用于遍历中缀表达式字符串
        String str; //用于多位数拼接
        char c; //每遍历到一个字符，就放入到c
        //开始遍历
        do {
            //将扫描的字符放到c
            c = s.charAt(i);
            //如果c是一个非数字
            if (!isNumber(c)){
                list.add("" + c);
                i++;
            }else {
                str = "";
                while (i < s.length() && isNumber(s.charAt(i))){
                    str += c;
                    i++;
                }
                list.add(str);
            }

        }while (i < s.length());
        return list;
    }

    public static boolean isNumber(char c){
        return c >= 48 && c <=57;
    }


    //计算逆波兰表达式
    public static void rpn(){
        String suffixExpression = "3 4 + 5 * 6 -";
        //思路
        //1.将3 4 + 5 * 6 - 放到ArrayList中
        //2.将ArrayList传递给一个方法，遍历ArrayList 配合桟 完成计算
        List<String> list = getListString(suffixExpression);
        int res = calculate(list);
        System.out.println("计算结果是：" + res);
    }

    public static List<String> getListString(String suffixExpression){
        //将suffixExpression分割
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    public static int calculate(List<String> list){
        Stack<String> stack = new Stack<>();
        for (String item : list) {
            if (item.matches("\\d+")){
                stack.push(item);
            }else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int result = 0;
                if ("+".equals(item)){
                    result = num1 + num2;
                }else if ("-".equals(item)){
                    result = num2 - num1;
                }else if ("*".equals(item)){
                    result = num1 * num2;
                }else if ("/".equals(item)){
                    result = num2 / num1;
                }else {
                    throw new RuntimeException("运算符错误");
                }

                stack.push("" + result);
            }
        }

        return Integer.parseInt(stack.pop());
    }
}


class Operator{
    public static int getPriority(String operator){
        int priority = 0;
        switch (operator){
            case "+":
            case "-":
                priority = 1;
                break;
            case "*":
            case "/":
                priority = 2;
                break;
            default:
                System.out.println("没有匹配到运算符");
                break;
        }
        return priority;
    }
}